\documentclass{classrep}
\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{graphicx}
\usepackage{placeins}
%\usepackage{caption}
%\usepackage{subcaption}
\usepackage{subfig}

\studycycle{Informatyka, studia dzienne, II st.}
\coursesemester{III}

\coursename{Nowoczesne Techniki Programowania}
\courseyear{2013/2014}

\courseteacher{Dariusz Puchała, Kamil Stokfiszewski}
\coursegroup{czwartek, 14:15}

\author{
  \studentinfo{Rafał Mościński}{nr 186844} \and
  \studentinfo{Marcin Kubczak}{nr 186834} 
}

\title{Zadanie Numer 2: Przeszukiwanie liniowe i binarne.}

\begin{document}
\maketitle

\section{Cel}
{ 
Zadanie dotyczy analizy algorytmów przeszukiwania liniowego i binarnego. W ramach analizy stwierdzono kiedy stosowanie jednej oraz drugiej metody jest opłacalne.
 }

\section{Wprowadzenie}
{

\subsection{Przeszukiwanie liniowe}
Przeszukiwanie liniowe polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych takich jak tablica w celu znalezienia zadanego klucza. Liczba porównań zależna jest od położenia szukanego elementu tablicy i wynosi od 1 do n, gdzie n to całkowita liczba elementów w tablicy. Złożoność algorytmu wynosi O(n).

\subsection{Przeszukiwanie binarne}
Przeszukiwanie binarne polega na dzieleniu uporządkowanej tablicy na pół następnie zawężanie przedziału poszukiwań od początku tablicy do elementu środkowego w przypadku gdy wartość szukanego klucza jest mniejsza od środkowego elementu lub od środkowego elementu do końca tablicy w przeciwnym wypadku. Przedziały zawężane są tak długo aż otrzymany zostanie jeden element, lub element wyznaczający środek jest równy poszykiwanemu. Złożoność algorytmu wynosi O(log(n)).

\section{Opis implementacji}
{
Aplikacja napisana została w języku Java. Do pomiaru czasu wykorzystano funkcję nanoTime() klasy System dostarczanej przez bibliotekę Java, która odczytuje wartość wewnętrznego licznika systemowego pomiaru czasu.
}

\section{Materiały i metody}
{
W celu oceny opłacalności stosowania poszczególnych algorytmów. Wykonano testy przeszukiwania tablicy jednowymiarowej o różnych długościach i zmierzono czas potrzebny na ukończenie algorytmu. Wykorzystano do tego javową funkcję nanoTime() klasy System. Wyniki zestawiono w tabeli, następnie narysowano wykresy obrazujące czas wykonania poszczególnych algorytmów w zależności od ilości elmentów w tablicy. Rozważono przypadek optymistyczny(szukany element znajdujący się w pierwszym kwantylu), przypadek normalny (szukany element w okolicach środka tablicy) oraz pesymistyczny (szukany element znajduje się w czwartym kwantylu tablicy.

W poniższej tabeli przedstawiono parametry dla jakich wykonano eksperymenty:

\begin{table}[h!]
\centering
\caption{Zbadane warianty}

\begin{tabular}{|c|c|}
\hline
 & Pozycja szukanego \\
Wielkość tablicy & elementu w tablicy   \\
\hline
%100 & 0.1 \\
%100 & 0.5   \\
%100 & 0.9  \\
%1000 & 0.1  \\
%1000 & 0.5  \\
%1000 & 0.9   \\
10000 &  0.1   \\
10000 & 0.5   \\
10000 & 0.9  \\
100000 & 0.1  \\
100000 & 0.5  \\
100000 & 0.9  \\
1000000 & 0.1  \\
1000000 & 0.5 \\
1000000 & 0.9   \\
\hline
\end{tabular} 

\end{table}

}
\section{Wyniki}
{

Poniżej przedstawiono wyniki jakie otrzymano oraz wykresy obrazujące je (opisane w poprzednim rozdziale):

\newpage
Przypadek  optymalny (szukany element znajduje się na pozycji 0.1 tablicy:

\FloatBarrier
\begin{figure}[h!]
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=\textwidth]{10000e0_1.png}
\caption{Rozmiar tablicy do 10 000 elementów, skok o 10}
\label{fig:figure1}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=\textwidth]{100000e0_1.png}
\caption{Rozmiar tablicy do 100 000 elementów, skok o 100}
\label{fig:figure2}
\end{minipage}
\end{figure}
\FloatBarrier
\begin{figure}[ht!]
\centering
\includegraphics[width=70mm]{100000e0_1.png}
\caption{Rozmiar tablicy do 1 000 000 elementów, skok o 1000}
\label{fig:figure3}
\end{figure}

\newpage
Przypadek  średni (szukany element znajduje się na pozycji 0.5 tablicy):
\FloatBarrier
\begin{figure}[h!]
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=\textwidth]{10000e0_5.png}
\caption{Rozmiar tablicy do 10 000 elementów, skok o 10}
\label{fig:figure4}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=\textwidth]{100000e0_5.png}
\caption{Rozmiar tablicy do 100 000 elementów, skok o 100}
\label{fig:figure5}
\end{minipage}
\end{figure}
\FloatBarrier
\begin{figure}[ht!]
\centering
\includegraphics[width=70mm]{100000e0_5.png}
\caption{Rozmiar tablicy do 1 000 000 elementów, skok o 1000}
\label{fig:figure6}
\end{figure}

\newpage
Przypadek pesymistyczny (szukany element znajduje się na pozycji 0.9 tablicy):
\FloatBarrier
\begin{figure}[h!]
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=\textwidth]{10000e0_9.png}
\caption{Rozmiar tablicy do 10 000 elementów, skok o 10}
\label{fig:figure7}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=\textwidth]{100000e0_9.png}
\caption{Rozmiar tablicy do 100 000 elementów, skok o 100}
\label{fig:figure8}
\end{minipage}
\end{figure}
\FloatBarrier
\begin{figure}[ht!]
\centering
\includegraphics[width=70mm]{100000e0_9.png}
\caption{Rozmiar tablicy do 1 000 000 elementów, skok o 1000}
\label{fig:figure9}
\end{figure}

\section{Dyskusja i wnioski}
{
%Na podstawie uzyskanych pomiarów obliczono, że złożoność algorytmu quicksort w zależności od ilości elementów jest następującego rzędu:
%\begin{itemize}
%\item Dla przypadku optymistycznego:
%\begin{equation}
%Time(n)=O(nlog_2n)
%\end{equation} 
%\item Dla przypadku pesymistycznego:
%\begin{equation}
%Time(n)=O(n^2)
%\end{equation}
%\end{itemize}
}

Powyższe ekesperymenty pokazały, że opłacalność użycia algorytmu przeszukiwania binarnego bardzo dynamicznie wzrasta w miarę zwiększania rozmiaru tablicy. Rozmiarem tablicy będącym na granicy opłacalności używania algorytmu liniowego w stosunku do algorytmu binarnego jest rozmiar ok 2000 elementów. Wyniki te pokrywają się z intuicją. Znacznie krótszy czas obliczeń algorytmu binarnego w miarę zwiększania rozmiaru tablicy wynika z tego, że algorytm ten ma złożoność logarytmiczną zatem przykładowo dla tablicy mającej milion elementów maksymalna ilość przeszukiwań wynosi log2(1000000)= 19.93 gdzie w przypadku alogorytmu liniowego maksymalna ilość przeszukiwań może wynieść milion. Różnica czasowa dla przypadku pesymistycznego widoczna jest na wykresie \ref{fig:figure9}. Dla tablicy o 1 mln elementów wyniosła ona około 180 ms, czyli 150-cio krotnie wiecej od przeszukiwania binarnego.

\begin{thebibliography}{0}
\item Materiały wykładowe. Wykład 2.
\end{thebibliography}
\end{document}
